package com.miracle;

/**
 *
 *  直方图的水量
 *
 *  给定一个直方图(也称柱状图)，假设有人从上面源源不断地倒水，最后直方图能存多少水量?直方图的宽度为 1。
 *
 *
 *  输入: [0,1,0,2,1,0,1,3,2,1,2,1]
 * 输出: 6
 *
 * @author : miracle
 * @version : 1.0.0
 * @date : 2021/4/2 19:38
 */
public class Trap {

    public static void main(String[] args) {
        int[] height = {0,1,0,2,1,0,1,3,2,1,2,1};
        System.out.println(trap(height));
    }

    /**
     * 解题思路
     * 1. 找到最大值和最大值的下标
     * 2. 然后左右计算面积
     *  左 = max * maxIndex-1 - 需要减去的面积
     *  右 = max * (length - maxIndex) - 需要减去的面积
     * 第二步的关键时如何计算需要减去的面积
     * @param height
     * @return
     */
    public static int trap(int[] height) {
        // 找到最大值
        int max = 0;
        int maxIndex = 0;
        for (int i = 0; i < height.length; i++) {
            if (height[i] > max) {
                max = height[i];
                maxIndex = i;
            }
        }
        // 左循环
        int temp = 0;
        int rub = 0;
        for (int i = 0; i < maxIndex; i++) {
            if (height[i] > temp) {
                temp = height[i];
            }
            rub += height[i] + (max - temp);
        }
        // 左边总数
        int leftCount = max * (maxIndex - 1) - rub;

        temp = 0;
        rub = 0;
        for (int i = height.length - 1; i > maxIndex; i--) {
            if (height[i] > temp) {
                temp = height[i];
            }
            rub += height[i] + (max - temp);
        }
        // 右边总数
        int rightCount = max * (height.length - maxIndex) - rub;

        return leftCount + rightCount;
    }
}
